package com.xy6.algo.sort;

import java.util.Arrays;

/**
 * 快速排序
 * <pre>
 * 时间复杂度：O(nlgn)，空间复杂度：O(n+2)
 * 
 * 取数组a第一个元素作为基准pivot，与最后一个元素进行交换
 * 定义变量left=0，表示第一个元素索引，right=n-1，表示最后一个元素索引
 * 遍历子序列[left,right]，定义变量flag，初始值为子序列第一个元素索引
 * 当前元素索引为i，比较a[i]与pivot大小，如果大于等于，则无需处理，继续遍历；
 * 如果小于，将a[i]与a[flag]进行交换，实现大于基准值的元素前移，将flag加1。使flag指向下一个比pivot大的元素
 * 遍历完毕，将a[flag]与pivot进行交换，实现将基准值放在[比pivot小的元素集合]、[比pivot大的元素集合]中间
 * 遍历子序列[left,flag-1]，处理步骤如上，递归处理
 * 遍历子序列[flag+1,right]，处理步骤如上，递归处理
 * 遍历完毕后，数组已按从小到大排序
 * 
 * 最坏时间复杂度为O(n^2)，最优时间复杂度为O(nlgn)
 * 不稳定排序
 * </pre>
 * 
 * @author zhang
 * @since 2017-07-23
 */
public class SortQuick {

	public static void main(String[] args) {
		int[] arr = new int[] { 1, 3, 5, 2, 4, 6 };
		sort(arr);
		System.out.println(Arrays.toString(arr));
	}
	
	public static void sort(int[] arr){
		sort(arr, 0, arr.length - 1);
	}
	
	/**
	 * 递归排序
	 * <p>交换元素，实现小的在左边，大的在右边
	 * 
	 * @param arr
	 * @param leftIndex
	 * @param rightIndex
	 */
	private static void sort(int[] arr, int leftIndex, int rightIndex){
		if(leftIndex >= rightIndex || leftIndex < 0 || rightIndex < 0){
			return;
		}
		
		// 基准元素
		int pivot = arr[leftIndex];
		// 将基准元素移到末尾
		int temp = arr[leftIndex];
		arr[leftIndex] = arr[rightIndex];
		arr[rightIndex] = temp;
		
		// 标记待交换元素索引
		int flag = leftIndex;
		for (int i = leftIndex; i <= rightIndex - 1; i++) {
			if(arr[i] >= pivot){
				continue;
			}
			// 前面元素均比基准值小，无需交换
			if(flag == i){
				flag++;
				continue;
			}
			temp = arr[flag];
			arr[flag] = arr[i];
			arr[i] = temp;
			flag++;
		}
		
		// 将比基准元素小的最后元素的后一个元素，移到末尾
		temp = arr[flag];
		arr[flag] = arr[rightIndex];
		arr[rightIndex] = temp;
			
		sort(arr, leftIndex, flag - 1);
		sort(arr, flag + 1, rightIndex);
	}
	
	
}
